package tree;

import offer.TreeNode;

import java.util.*;

/**
 * 给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
 *
 * 两棵树重复是指它们具有相同的结构以及相同的结点值。
 *
 * 示例 1：
 *
 *         1
 *        / \
 *       2   3
 *      /   / \
 *     4   2   4
 *        /
 *       4
 * 下面是两个重复的子树：
 *
 *       2
 *      /
 *     4
 * 和
 *
 *     4
 *
 */
public class leetCode652_findDuplicateSubtrees {
    HashMap<String,Integer> mem = new HashMap<>();
    List<TreeNode> result = new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        build(root);
        return result;
    }
    public String build(TreeNode root) {

        if(root == null){
            return "#";
        }
        String left = build(root.left);
        String right = build(root.right);

        String tag =left + "," + right+ "," + root.val;
        int freq = mem.getOrDefault(tag, 0);
        if(freq == 1){
            result.add(root);
        }
        mem.put(tag,freq + 1);
        return tag;
    }

    HashMap<String,Integer> mem2= new HashMap<>();
    List<TreeNode> result2 = new ArrayList<>();
    public List<TreeNode> findDuplicateSubtrees2(TreeNode root) {
        if(root == null) return  null;
        tranverse(root);
        return result2;
    }
    public String tranverse(TreeNode root){

        if(root == null) return "#";

        String left = tranverse(root.left);
        String right = tranverse(root.right);
        // 这里的拼接顺序，root不能放中间
        String tag =left + "," + right+ "," + root.val;
        if(mem2.getOrDefault(tag,0) == 1){
            result2.add(root);
        }
        mem2.put(tag,mem2.getOrDefault(tag,0) + 1);
        return tag;
    }


}
